The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
Token buckets are used in a computer or communications system for controlling rates at which corresponding items are processed (e.g., number of bytes of packets sent, processing time of computer processes, etc.). The number of tokens in a token bucket identifies the amount of processing that is available for the corresponding item. If a token bucket does not have enough tokens needed for the requisite next processing of an item, an item is ineligible for processing. Thus, the processing of the item may be forgone (e.g., packet(s) dropped) or delayed at least until the token bucket acquires enough tokens. Tokens are typically added periodically.
Prior known systems typically use a single memory location for storing the entire number of tokens in a token bucket, with this memory location residing on or off the processing chip. Systems using a large number of token buckets require a proportionally large memory space to store each of the token buckets, and thus typically use a memory device (e.g., RAM) external to the processing system. This can be problematic for high speed applications, in which the bandwidth required to access these memory locations is not available for the required high access rate, and thus, needed are new approaches for maintaining the tokens in token buckets.
A prior system maintains incrementing statistic counters according to the approach described in Srinivasa Rao Malladi and Earl T. Cohen, “Methods and Apparatus for Maintaining Statistic Counters and Updating a Secondary Counter Storage Via a Queue For Reducing or Eliminating Overflow of the Counters,” U.S. patent application Ser. No. 10/295,181, filed Nov. 15, 2002, (hereinafter “Malladi et al.”). The statistic counters used in the prior system only increase in value, and the approach implemented in this prior art system cannot be used for maintaining the number of tokens in a token bucket which can both increase and decrease in the value. This prior art system is believed to teach away from maintaining portions of a value among multiple storage locations with values that can be incremented and decremented by amounts corresponding to an amount of processing, as Malladi et al. provides no mechanism for performing such function and provides no rational for desiring to perform such function. Note, an embodiment of the invention described in Malladi et al. has been used in publicly disclosed and sold products for over a year prior to filing of this patent application.